package Algorithm;

import java.util.Arrays;

public class maxSum {
    public static int maxSumOfMatrix(int[][] matrix){
        int beginRow=0; //以它为起始行
        final int M=matrix.length;
        final int N=matrix[0].length;
        int[] sums=new int[N]; //按列求和
        int max=0;// 历史最大的子矩阵和
        while(beginRow<M){ //起始行
            for(int i=beginRow;i<M;i++){ //从起始行到第i行
                for(int j=0;j<N;j++){
                    sums[j]+=matrix[i][j];
                }
                //累加完成
                int sum=sums[0];
                int max2=sum;
                for(int j=1;j<sums.length;j++){
                    if(sum>=0){
                        sum+=sums[j];
                    }else{
                        sum=sums[j];
                    }
                    if(sum>max2){
                        max2=sum;
                    }
                }
                if(max2>max)max=max2;
            }
            Arrays.fill(sums,0);
            beginRow++;
        }
        return max;
    }
    public static void main(String[] args) {
        int[][] matrix=new int[][]{{-1,-1,-1},{-1,2,2},{-1,-1,-1}};
        System.out.println(maxSumOfMatrix(matrix));
    }
}
